package main

import "container/list"

type TreeNode struct {
	Val    any
	Left   *TreeNode
	Right  *TreeNode
	Height int
}

// NewTreeNode creates a new TreeNode with the given data.
func NewTreeNode(data any) *TreeNode {
	return &TreeNode{
		Val:   data,
		Left:  nil,
		Right: nil,
	}
}

func CreateSampleTree() *TreeNode {
	n1 := NewTreeNode(1)
	n2 := NewTreeNode(2)
	n3 := NewTreeNode(3)
	n4 := NewTreeNode(4)
	n5 := NewTreeNode(5)
	n6 := NewTreeNode(6)
	n7 := NewTreeNode(7)
	n1.Left = n2
	n1.Right = n3
	n2.Left = n4
	n2.Right = n5
	n3.Left = n6
	n3.Right = n7
	return n1
}

func PreOrder(node *TreeNode, nums *[]any) {
	if node == nil {
		return
	}
	// access priority: root node -> left node -> right node
	*nums = append(*nums, node.Val)
	PreOrder(node.Left, nums)
	PreOrder(node.Right, nums)
}

func InOrder(node *TreeNode, nums *[]any) {
	if node == nil {
		return
	}
	// access priority:  left node -> root node -> right node
	InOrder(node.Left, nums)
	*nums = append(*nums, node.Val)
	InOrder(node.Right, nums)
}

func PostOrder(node *TreeNode, nums *[]any) {
	if node == nil {
		return
	}
	// access priority:  left node -> right node -> root node
	PostOrder(node.Left, nums)
	PostOrder(node.Right, nums)
	*nums = append(*nums, node.Val)
}

// LevelOrder performs a level-order traversal (breadth-first traversal) on a binary tree.
func LevelOrder(tree *TreeNode) (res []any) {
	if tree == nil {
		return res
	}

	queue := list.New()
	queue.PushBack(tree)
	for queue.Len() > 0 {
		node := queue.Remove(queue.Front()).(*TreeNode)
		res = append(res, node.Val)
		if node.Left != nil {
			queue.PushBack(node.Left)
		}
		if node.Right != nil {
			queue.PushBack(node.Right)
		}
	}
	return res
}

type TreeArr struct {
	Val []any
}

func NewTreeArr(val []any) *TreeArr {
	return &TreeArr{
		Val: val,
	}
}

func (t *TreeArr) Size() int {
	return len(t.Val)
}

func (t *TreeArr) Get(i int) any {
	if i < 0 || i >= t.Size() {
		return nil
	}

	return t.Val[i]
}

func (t *TreeArr) Left(i int) int {
	return 2*i + 1
}

func (t *TreeArr) Right(i int) int {
	return 2*i + 2
}

func (t *TreeArr) Parent(i int) int {
	// 向下取整
	return (i - 1) / 2
}

// LevelOrder traverses the binary tree in level order and returns a slice
// containing the values of the nodes. It skips any nil values in the tree.
func (t *TreeArr) LevelOrder() []any {
	var res []any
	for _, v := range t.Val {
		if v != nil {
			res = append(res, v)
		}
	}
	return res
}

func (t *TreeArr) dfs(i int, order string, res *[]any) {
	if t.Get(i) == nil {
		return
	}

	if order == "pre" {
		*res = append(*res, t.Val[i])
	}
	t.dfs(t.Left(i), order, res)
	if order == "in" {
		*res = append(*res, t.Val[i])
	}
	t.dfs(t.Right(i), order, res)
	if order == "post" {
		*res = append(*res, t.Val[i])
	}

}

func (t *TreeArr) PreOrder() []any {
	var res []any
	t.dfs(0, "pre", &res)
	return res
}

func (t *TreeArr) InOrder() []any {
	var res []any
	t.dfs(0, "in", &res)
	return res
}
func (t *TreeArr) PostOrder() []any {
	var res []any
	t.dfs(0, "post", &res)
	return res
}
